class _Node {
    val: number
    next: _Node | null
    random: _Node | null

    constructor(val?: number, next?: _Node | null, random?: _Node | null) {
        this.val = (val === undefined ? 0 : val)
        this.next = (next === undefined ? null : next)
        this.random = (random === undefined ? null : random)
    }
}
function copyRandomList(head: _Node | null): _Node | null {
    if (!head) return null;

    // 创建原节点到复制节点的映射
    const map = new Map<_Node, _Node>();
    let current: _Node | null = head;

    // 第一遍遍历：创建所有新节点，建立映射关系
    while (current) {
        map.set(current, new _Node(current.val));
        current = current.next;
    }

    // 第二遍遍历：设置 next 和 random 指针
    current = head;
    while (current) {
        const copyNode = map.get(current)!;

        // 设置 next 指针
        if (current.next) {
            copyNode.next = map.get(current.next)!;
        }

        // 设置 random 指针
        if (current.random) {
            copyNode.random = map.get(current.random)!;
        }

        current = current.next;
    }

    return map.get(head)!;
};